Theo địa bạ An Giang được xác lập ngày mùng 3 tháng 6 năm Minh Mệnh thứ 17 (Dương lịch 1836), thôn Vĩnh Lộc thuộc tổng An Lương, huyện Đông Xuyên, phủ Tuy Biên[3].

Ngày 8 tháng 5 năm 1928, chính quyền thực dân Pháp cho lập các xã mới (trước đó là thôn, làng) ở Nam Kỳ. Theo đó, lập mới xã Vĩnh Lộc (từ thôn Vĩnh Lộc) thuộc tổng An Phú.[4]

Đến thời Việt Nam Cộng hòa, tổng An Phú và 4 xã của tổng Châu Phú được tách ra khỏi quận Châu Phú để thành lập quận An Phú thuộc tỉnh An Giang, xã Vĩnh Lộc thuộc quận An Phú. Năm 1964, tỉnh Châu Đốc được tái lập, quận An Phú thuộc tỉnh Châu Đốc.

Sau năm 1975, quận An Phú sáp nhập với quận Tân Châu thành huyện Phú Châu, xã Vĩnh Lộc thuộc huyện Phú Châu.

Ngày 12 tháng 1 năm 1984, Hội đồng Bộ trưởng ban hành Quyết định số 8-HĐBT[5]. Theo đó, sáp nhập một phần ấp 1 của xã Vĩnh Lộc vào xã Phú Hữu.

Ngày 13 tháng 11 năm 1991, huyện Phú Châu được chia lại thành hai huyện An Phú và Tân Châu, xã Vĩnh Lộc thuộc huyện An Phú.

Ngày 24 tháng 8 năm 2009, Chính phủ ban hành Nghị quyết số 40/NQ-CP[2]. Theo đó, điều chỉnh 513 ha diện tích tự nhiên và 1.415 người của xã Phú Lộc, huyện Tân Châu về xã Vĩnh Lộc quản lý.

Sau khi điều chỉnh địa giới hành chính, xã Vĩnh Lộc có 4.116 ha diện tích tự nhiên và 13.688 người.